package com.lw.leetcode.arr.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 面试题 17.18. 最短超串
 *
 * @Author liw
 * @Date 2021/10/2 21:20
 * @Version 1.0
 */
public class ShortestSeq {

    public static void main(String[] args) {
        ShortestSeq test = new ShortestSeq();
        // [7,10]
//        int[] arr =  {7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7};
//        int[] arr2 =  {1,5,9};
        // [7,10]
//        int[] arr =  {1,2,3};
//        int[] arr2 =  {3,1};
        // [1,1]
        int[] arr = {878982, 143504, 268583, 394343, 849567, 257687, 352256, 35131, 663529, 543027};
        int[] arr2 = {143504};
        int[] ints = test.shortestSeq(arr, arr2);
        System.out.println(Arrays.toString(ints));
    }

    public int[] shortestSeq(int[] big, int[] small) {
        int length = small.length;
        int bigLenght = big.length;
        int count = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i : small) {
            map.put(i, -1);
        }
        Integer value;
        int i = 0;
        for (; i < bigLenght; i++) {
            value = map.get(big[i]);
            if (value == null) {
                continue;
            }
            map.put(big[i], i);
            if (value == -1) {
                count++;
                if (count == length) {
                    break;
                }
            }
        }
        if (count < length) {
            return new int[0];
        }
        int max = i;
        int min = 0;
        for (int j = 0; j <= i; j++) {
            if (map.get(big[j]) != null && map.get(big[j]) == j) {
                min = j;
                break;
            }
        }
        int[] arr = {min, max};
        for (int j = i + 1; j < bigLenght; j++) {
            if (map.get(big[j]) != null) {
                map.put(big[j], j);
                for (int k = min; k < bigLenght; k++) {
                    if (map.get(big[k]) != null && map.get(big[k]) == k) {
                        min = k;
                        if (j - k < arr[1] - arr[0]) {
                            arr[0] = k;
                            arr[1] = j;
                        }
                        break;
                    }
                }
            }
        }
        return arr;
    }
}
